package Test;

import java.util.Stack;

public class Test4 {
    public static int max1(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int minNum = Integer.MAX_VALUE;
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                    minNum = Math.min(minNum, arr[k]);
                }
                max = Math.max(max, minNum * sum);
            }
        }
        return max;
    }

    public static int max2(int[] arr) {
        int size = arr.length;
        int[] sums = new int[size];
        sums[0] = arr[0];
        for (int i = 1; i < size; i++) {
            sums[i] = sums[i - 1] + arr[i];
        }
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                int j = stack.pop();
                max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
                if(max == 10374)
                    System.out.println(j);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int j = stack.pop();
            max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
            if(max == 10374)
                System.out.println(j);
        }
        return max;
    }

    public static int[] gerenareRondomArray() {
        int[] arr = new int[(int) (Math.random() * 20) + 10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 101);
        }
        return arr;
    }

    public static void main(String[] args) {
//        int testTimes = 2000000;
//        for (int i = 0; i < testTimes; i++) {
//            int[] arr = gerenareRondomArray();
//            if (max1(arr) != max2(arr)) {
//                System.out.println("FUCK!");
//                break;
//            }
//        }
        int[] nums = {36,9,13,27,43,25,44,48,12,40,37,20,26,36,1,20,19,14,28,38,39,42,21,30,29,29,44,14,33,31,48,11,43,6,19,33,43,41,40,22,6,49,16,44,20,15,13,10,2,3,16,31,40,50,5,30,27,41,37,13,46,45,25,32,26,16,10,42,45,1,49,50,7,50,28,15,12,45,34,30,4,36,16,8,30,9,30,43,34,36,39,21,49,29,40,47,33,28,36,29};
        int res = max2(nums);
        System.out.println(res);
        int[] nums2 = {2,5,4,2,4,5,3,1,2,4};
        int res2 = max2(nums2);
        System.out.println(res2);

    }
}
